#include <stdio.h>

#define N 8
//#define PRINT_CHESS

int Q[N];
int ResultCount = 0;

void printArray(int* a, int len)
{
	int i;
	for (i = 0; i < len; ++i)
	{
		printf("%d\t", a[i]);
	}
	printf("\n");
}

void printChess()
{
	int i, j;
	++ResultCount;
#ifdef PRINT_CHESS
	printf("........%d................\n", ResultCount);
	for (i = 0; i < N; ++i)
	{
		for (j = 0; j < N; ++j)
		{
			if (Q[i] == j)
				printf("X ");
			else
				printf("O ");
		}
		printf("\n");
	}
	printf("........................\n");
#endif
}

void computeM(int* m, int level)
{
	int i, delta;
	for (i = 0; i < level; ++i)
	{
		delta = level - i;
		m[ Q[i] ] = 0;
		delta = level - i;
		if (Q[i] + delta < N)
		{
			m[ Q[i] + delta ] = 0;
		}
		if (Q[i] - delta >= 0)
		{
			m[ Q[i] - delta ] = 0; 
		}
	}
}

void queen(int level)
{
	if (level >= N)
	{
		printChess();
		return;		
	}

	int i;
	int m[N];
	for (i = 0; i < N; ++i)
	{
		m[i] = 1;
	}

	computeM(&m, level);

	for (i = 0; i < N; ++i)
	{
		if (m[i] == 0)
		{
			continue;
		}
		Q[level] = i;
		queen(level+1);
	}
}

int main(void)
{
	int i;
	for (i = 0; i  < N; ++i)
	{
		Q[i] = -1;
	}
	printf("这是一种递归的解法:\n");
	printf("----------------------\n");
	queen(0);
	printf("共%d种放法.\n", ResultCount);
	printf("----------------------\n");

	printf("非递归的解法:\n待完成。\n");

	return 0;
}
